public class test {
    //leetcode 647.回文子串
    class Solution {
        public int countSubstrings(String s) {
            // 1. 创建dp表
            int n = s.length();
            char[] nums = s.toCharArray();
            //代表截取[i,j]的字符串是否为回文子串
            boolean[][] dp = new boolean[n][n];
            int sum = 1;
            // 2. 初始化

            // 3. 填表
            for(int i = n - 2;i >= 0;i--){
                for(int j = i;j < n;j++){
                    if(nums[i] == nums[j]){
                        if(i == j || i + 1 == j){
                            dp[i][j] = true;
                        }else {
                            dp[i][j] = dp[i+1][j-1];
                        }
                    }else {
                        dp[i][j] = false;
                    }
                    if(dp[i][j]){
                        sum++;
                    }
                }
            }
            // 4. 返回值
            return sum;
        }
    }
    //leetcode 5. 最长回文子串
    class Solution {
        public String longestPalindrome(String s) {
            // 1. 创建dp表
            int n = s.length();
            char[] nums = s.toCharArray();
            boolean[][] dp = new boolean[n][n];
            int number = 1;
            int begin = 0;
            int end = 0;
            // 2. 初始化

            // 3. 填表
            // abccaccbab
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (nums[i] == nums[j]) {
                        dp[i][j] = (i + 1 < j) ? dp[i+1][j-1] : true;
                    }
                    if (dp[i][j] && j - i + 1 > number) {
                        number = j - i + 1;
                        begin = i;
                        end = j;
                    }
                }
            }
            // 4. 返回值
            return s.substring(begin,end + 1);
        }
    }
    //leetcode 1745.分割回文串Ⅱ
    class Solution {
        public int minCut(String s) {
            // 1. 创建dp[]表
            int n = s.length();
            char[] nums = s.toCharArray();
            //代表[i，j]范围内的子串是否为回文字符串
            boolean[][] dp = new boolean[n][n];
            //代表[0~i]位置最长子串的最少分割次数
            int[] dp1 = new int[n];
            // 2. 初始化

            // 3. 填表
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (nums[i] == nums[j]) {
                        dp[i][j] = (i + 1 < j) ? dp[i + 1][j - 1] : true;
                    }
                }
            }
            Arrays.fill(dp1,Integer.MAX_VALUE);
            for(int i = 0;i < n;i++){
                if(dp[0][i]){
                    dp1[i] = 0;
                }else{
                    int index = i;
                    for(int j = 1;j <= i;j++){
                        if(dp[j][i]){
                            dp1[i] = Math.min(dp1[i],dp1[j - 1] + 1);
                        }
                    }
                }
            }
            // 4. 返回值
            return dp1[n - 1];
        }
    }
}
